import java.util.Arrays;

public class MaxHeap {
    int[] maxHeap;
    int UsedSize;
    int Capacity;
    static int DEFAULT_CAPACITY = 10;
    public MaxHeap(){
        this(DEFAULT_CAPACITY);
    }
    public MaxHeap(int cap){
        maxHeap = new int[cap];
        Capacity = cap;
        maxHeap[0] = 0;
    }
    public void add(int element){
        checkCapacity();
        maxHeap[++UsedSize] = element;
        shiftUp();
    }
    public int peek(){
        if(isEmpty()){
            return Integer.MIN_VALUE;
        }else{
            return maxHeap[1];
        }
    }
    public int pop(){
        if(isEmpty()){
            return Integer.MIN_VALUE;
        }
        int tem = maxHeap[1];
        maxHeap[1] = maxHeap[UsedSize--];
        shiftDown();
        return tem;
    }
    public int size(){
        return UsedSize;
    }
    private void shiftDown(){
        int index = 1;
        while(index<UsedSize && index<=UsedSize/2){
            int target = maxHeap[index*2]>maxHeap[index*2+1]?index*2:index*2+1;
            if(maxHeap[index]<maxHeap[target]){
                swap(maxHeap,index,target);
            }else{
                break;
            }
        }
    }
    private void shiftUp(){
        int index = UsedSize;
        int parent = index/2;
        while(maxHeap[index]>maxHeap[parent] && index>1){
            swap(maxHeap,index,parent);
            index = parent;
            parent = index/2;
        }
    }
    private void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }
    private void checkCapacity(){
        if(UsedSize==Capacity){
            maxHeap = Arrays.copyOf(maxHeap,Capacity*2);
            Capacity *= 2;
        }
    }
    public String toString() {
        if (UsedSize == 0) {
            return "No element!";
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = 1; i <= UsedSize; i++) {
                sb.append(maxHeap[i]);
                sb.append(',');
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append(']');
            return sb.toString();
        }
    }
    public boolean isEmpty(){
        return UsedSize==0;
    }

    public static void main(String[] args) {
        // 测试用例
        MaxHeap maxheap = new MaxHeap(5);
        maxheap.add(1);
        maxheap.add(2);
        maxheap.add(3);
        // [3,1,2]
        System.out.println(maxheap.toString());
        // 3
        System.out.println(maxheap.peek());
        // 3
        System.out.println(maxheap.pop());
        System.out.println(maxheap.pop());
        System.out.println(maxheap.pop());
        // No element
        System.out.println(maxheap.toString());
        maxheap.add(4);
        // Add too mant elements
        maxheap.add(5);
        // [4,1,2]
        System.out.println(maxheap.toString());



    }




}
